package interview.questions.最长的回文串;

/**
 * 问题：
 * <p>
 * 从给出的字符串中求出由这些字母构成的最长的回文串
 */
public class Solution {
    //就是统计一下每种字母出现的次数。偶数的都能用上，奇数个数少用一个。最后还有多的可以再放在中间一个。

    public static int longestPalindrome0(String s) {
        if(s==null || s.length()==0) return 0;
        int[] bucket = new int[60];    //A:65  z：122

        for(char c : s.toCharArray()){
            bucket[c-'A']++;
        }

        int cnt=0;
        int mid=0;
        for(int i=0;i<59;i++){
            if((bucket[i]&1) == 0){  //偶数
                cnt+=bucket[i];
            }else{                   //奇数
                cnt+=bucket[i]-1;
                mid=1;
            }
        }

        return cnt+mid;
    }

    public static int longestPalindrome1(String s) {
        if(s==null || s.length()==0) return 0;
        int[] bucket = new int[60];  //A:65  z：122

        for(char c : s.toCharArray()){
            bucket[c-'A']++;
        }

        int cnt=0;
        for(int num: bucket){
            cnt += num/2*2;  //0->0 1->0 2->2 3->2
        }

        return cnt<s.length()? cnt+1 : cnt;
    }


}
